package net.flintx.array;

import java.util.Arrays;

/**
 * Created by flintx on 2018/1/14.
 */
public class MaxAreaOfIsland {

    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length;
        if (m < 1)
            return 0;
        int n = grid[0].length;
        if (n < 1)
            return 0;
        boolean[][] vis = new boolean[m][n];
        for (boolean[] v : vis)
            Arrays.fill(v, false);
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0 && !vis[i][j]) {
                    max = Math.max(max, dfs(grid, vis, i, j));
                }
            }
        }
        return max;
    }

    private int dfs(int[][] grid, boolean[][] vis, int x, int y) {
        if (!check(grid, x, y))
            return 0;
        else if (grid[x][y] == 0)
            return 0;
        else if (vis[x][y])
            return 0;
        vis[x][y] = true;
        return 1 + dfs(grid, vis, x + 1, y) + dfs(grid, vis, x, y + 1)
                + dfs(grid, vis, x - 1, y) + dfs(grid, vis, x,y - 1);
    }

    private boolean check(int[][] grid, int x, int y) {
        return !(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length);
    }

    public static void main(String[] args) {
        int[][] grid = {
                {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
                {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}
        };
        System.out.println(new MaxAreaOfIsland().maxAreaOfIsland(grid));
    }
}
